/**
 * Created by L.jp
 * Description:给定两个字符串 str1 和 str2 ，请你算出将 str1 转为 str2 的最少操作数。
 * 你可以对字符串进行3种操作：
 * 1.插入一个字符
 * 2.删除一个字符
 * 3.修改一个字符。
 * User: 86189
 * Date: 2022-09-03
 * Time: 16:32
 */
public class Solution {
    public int editDistance (String str1, String str2) {
        int len1=str1.length();
        int len2=str2.length();
        //dp表示str1[i]到str2[j]的编辑距离
        int[][] dp=new int[len1+1][len2+1];
        //初始化第一行和第一列，需要借助dp[0][0]来推导状态，dp[0][0]表示空串变为空串需要0步
        //第一行和第一列都表示由一个字符串变成一个空串需要多少步，那其实就是根据字符串的个数来决定的
        //初始化列
        for(int i=1;i<=len1;i++){
            dp[i][0]=dp[i-1][0]+1;
        }
        //初始化行
        for(int i=1;i<=len2;i++){
            dp[0][i]=dp[0][i-1]+1;
        }
        //构造数组
        for(int i=1;i<=len1;i++){
            for(int j=1;j<=len2;j++){
                //如果两个字符串对应的字符相等，那么编辑距离就不变
                if(str1.charAt(i-1)==str2.charAt(j-1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                }else{
                    //如果不相等，那就看增，删，改，三个步骤哪个方法使得编辑距离最短
                    //要根据前一个转态操作一步得到，所以就要+1
                    //dp[i-1][j-1]+1表示替换一步，dp[i-1][j]表示s1增加一步变成s2，dp[i][j-1]表示s1删除一步变成s2
                    dp[i][j]=Math.min(dp[i-1][j-1],Math.min(dp[i-1][j],dp[i][j-1]))+1;
                }
            }
        }
        return dp[len1][len2];
    }
}
